{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Collecting Chocolates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #收集巧克力"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 、下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标 <code>i</code> 的巧克力就对应第 <code>i</code> 个类型。</p>\n",
    "\n",
    "<p>在一步操作中，你可以用成本 <code>x</code> 执行下述行为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>同时修改所有巧克力的类型，将巧克力的类型&nbsp;<code>i<sup>th</sup></code>&nbsp;修改为类型&nbsp;<code>((i + 1) mod n)<sup>th</sup></code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [20,1,15], x = 5\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。\n",
    "接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。\n",
    "然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。\n",
    "因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], x = 4\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= x &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [collecting-chocolates](https://leetcode.cn/problems/collecting-chocolates/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [collecting-chocolates](https://leetcode.cn/problems/collecting-chocolates/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[20,1,15]\\n5', '[1,2,3]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        ans, n = sum(nums), len(nums)\n",
    "        mx = list(nums)\n",
    "        for i in range(1, n):\n",
    "            cnt = i * x\n",
    "            for j in range(n):\n",
    "                mx[j] = min(mx[j], nums[(j - i + n) % n])\n",
    "                cnt += mx[j]\n",
    "            ans = min(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        cur = nums[:]\n",
    "\n",
    "        ans = sum(cur)\n",
    "        for i in range(1, n):\n",
    "            nums = [nums[-1]] + nums[:-1]\n",
    "            for j, num in enumerate(nums):\n",
    "                cur[j] = min(cur[j], num)\n",
    "            ans = min(ans, sum(cur) + i * x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = nums.copy()\n",
    "        cost = 0\n",
    "        ret = sum(nums)\n",
    "        for i in range(1, n):\n",
    "            cost += x\n",
    "            s = 0\n",
    "            for j in range(n):\n",
    "                k = (j + i) % n \n",
    "                f[k] = min(f[k], nums[j])\n",
    "            ret = min(ret, sum(f) + cost)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = sum(nums)\n",
    "        cost = nums.copy()\n",
    "        for j in range(1, n):\n",
    "            for i in range(n):\n",
    "                cost[i] = min(cost[i], nums[(i-j)%n])\n",
    "            ans = min(ans, sum(cost) + x*j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))\n",
    "        for i, mn in enumerate(nums):\n",
    "            for j in range(i, n + i):\n",
    "                mn = min(mn, nums[j % n])\n",
    "                s[j - i] += mn\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = sum(nums)\n",
    "        tmp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                tmp[j] = min(nums[j], nums[(j + 1) % n])\n",
    "            ans = min(ans, sum(tmp) + i * x)\n",
    "            for j in range(n):\n",
    "                nums[j] = tmp[j]\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.minCost([20,1,15],5)\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n, m = len(nums) - 1, sum(nums)\n",
    "        for j in range(1, n + 1):\n",
    "            j *= x\n",
    "            if m <= j:\n",
    "                break\n",
    "            t = nums[0]\n",
    "            for i in range(n):\n",
    "                nums[i] = min(nums[i], nums[i + 1])\n",
    "            nums[-1] = min(nums[-1], t)\n",
    "            \n",
    "            m = min(m, sum(nums) + j)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        minn = nums[:]\n",
    "        for i in range(n):\n",
    "            cur = i * x\n",
    "            for j in range(n):\n",
    "                minn[j] = min(minn[j], nums[(j + i) % n])\n",
    "                cur += minn[j]\n",
    "            ans = min(ans, cur)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n, m = len(nums) - 1, sum(nums)\n",
    "        for j in range(1, n + 1):\n",
    "            t = nums[0]\n",
    "            for i in range(n):\n",
    "                nums[i] = min(nums[i], nums[i + 1])\n",
    "            nums[-1] = min(nums[-1], t)\n",
    "            m = min(m, sum(nums) + x * j)\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = sum(nums) # 不进行修改操作\n",
    "        tmp = [0] * n   # 进行某一次修改操作后的每个位置的最小值\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                tmp[j] = min(nums[j], nums[(j + 1) % n])\n",
    "            # 进行一次修改操作后需要更新nums\n",
    "            for j in range(n):\n",
    "                nums[j] = tmp[j]\n",
    "            ans = min(ans, sum(tmp) + i * x)\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.minCost([20,1,15],5)\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        ans = sum(nums)\n",
    "        n = len(nums)\n",
    "        tmp = copy.deepcopy(nums)\n",
    "        for k in range(1, n):\n",
    "            tmp = [min(tmp[i], nums[(i + k) % n]) for i in range(n)]\n",
    "            ans = min(ans, sum(tmp) + k * x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n=len(nums)\n",
    "        price,cost=list(nums),list(nums)\n",
    "        idx,cur=0,sum(nums)\n",
    "        res=cur\n",
    "        for i in range(1,n):\n",
    "            price.append(price[idx])\n",
    "            idx+=1\n",
    "            cur+=x\n",
    "            for j,k in enumerate(range(idx,len(price))):\n",
    "                if price[k]<cost[j]:\n",
    "                    cur-=cost[j]-price[k]\n",
    "                    cost[j]=price[k]\n",
    "            res=min(res,cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = nums.copy()\n",
    "        cost = 0\n",
    "        s = ret = sum(nums)\n",
    "        for i in range(1, n):\n",
    "            cost += x\n",
    "            for j in range(n):\n",
    "                k = (j + i) % n \n",
    "                if f[k] > nums[j]:\n",
    "                    s -= f[k] - nums[j]\n",
    "                    f[k] = nums[j]\n",
    "            ret = min(ret, cost + s)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        arr = nums[:]\n",
    "        tol = sum(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                arr[j] = min(arr[j], nums[(j + i) % n])\n",
    "            tol = min(tol, sum(arr) + i * x)\n",
    "        return tol\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        ans, n = sum(nums), len(nums)\n",
    "        mx = [i for i in nums]\n",
    "        for i in range(1, n):\n",
    "            cnt = i * x\n",
    "            for j in range(n):\n",
    "                mx[j] = min(mx[j], nums[(j - i + n) % n])\n",
    "                cnt += mx[j]\n",
    "            ans = min(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        n = len(nums)\n",
    "        a = [inf] * n\n",
    "        for k in range(n):\n",
    "            cur = k * x\n",
    "            for i in range(n):\n",
    "                a[i] = min(a[i], nums[(i - k) % n])\n",
    "                cur += a[i]\n",
    "            ans = min(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = nums[:]\n",
    "        result = sum(nums)\n",
    "        for t in range(1,n):\n",
    "            #操作t次\n",
    "            tmp = 0\n",
    "            for i in range(n):\n",
    "                dp[i] = min(dp[i],nums[(i+t)%n])\n",
    "                tmp += dp[i]\n",
    "            result = min(result, tmp+t*x)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = nums[:]\n",
    "        result = sum(nums)\n",
    "        for t in range(1,n):\n",
    "            #操作t次\n",
    "            tmp = 0\n",
    "            for i in range(n):\n",
    "                dp[i] = min(dp[i],nums[(i+t)%n])\n",
    "                tmp += dp[i]\n",
    "            result = min(result, tmp+t*x)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n*x , x))\n",
    "        for i,num in enumerate(nums):\n",
    "            for j in range(i,n+i):\n",
    "                num = min(num, nums[j%n])\n",
    "                s[j-i] += num   #j-i代表每次操作的次数，最小值离头数字越远，所减即为操作数\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  \n",
    "        for i, mn in enumerate(nums):\n",
    "            for j in range(i, n + i):  \n",
    "                mn = min(mn, nums[j % n]) \n",
    "                s[j - i] += mn \n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = nums[:]\n",
    "        result = sum(nums)\n",
    "        for t in range(1,n):\n",
    "            #操作t次\n",
    "            tmp = 0\n",
    "            for i in range(n):\n",
    "                dp[i] = min(dp[i],nums[(i+t)%n])\n",
    "                tmp += dp[i]\n",
    "            result = min(result, tmp+t*x)\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = list(range(0, n * x, x))\n",
    "        for i,num in enumerate(nums): \n",
    "            for j in range(i, i + n):\n",
    "                num = min(num, nums[j % n])\n",
    "                dp[j - i] += num\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n * x, x))  \n",
    "        for i, mn in enumerate(nums): \n",
    "            for j in range(i, n + i): \n",
    "                mn = min(mn, nums[j % n])  \n",
    "                s[j - i] += mn  \n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        min_values = [inf] * n\n",
    "        ans = inf\n",
    "        for k in range(n):\n",
    "            total = 0\n",
    "            for i,num in enumerate(nums):\n",
    "                if nums[(i - k + n) % n] < min_values[i]:\n",
    "                    min_values[i] = nums[(i - k + n) % n]\n",
    "                total += min_values[i]\n",
    "            total += k * x\n",
    "            ans = min(total, ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        k = [0] * (n + 1)\n",
    "        b = [0] * (n + 1)\n",
    "\n",
    "        def add(l: int, r: int, delta_k: int, delta_b: int):\n",
    "            k[l] += delta_k\n",
    "            k[r] -= delta_k\n",
    "            b[l] += delta_b\n",
    "            b[r] -= delta_b\n",
    "\n",
    "        add(0, n, x, 0)\n",
    "\n",
    "        min_num = min(nums)\n",
    "        min_index = nums.index(min_num)\n",
    "\n",
    "        add(0, n, min_num, min_num)\n",
    "\n",
    "        nums = [nums[(min_index + i) % n] for i in range(1, n)]\n",
    "\n",
    "        def f(a: List[int], left_less: True):\n",
    "            res = [0] * len(a)\n",
    "            stack = []\n",
    "            for i in range(len(a)):\n",
    "                while len(stack) and (\n",
    "                    a[stack[-1]] > a[i] or (a[stack[-1]] == a[i] and not left_less)\n",
    "                ):\n",
    "                    stack.pop()\n",
    "                if len(stack):\n",
    "                    res[i] = i - stack[-1] - 1\n",
    "                else:\n",
    "                    res[i] = i\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "        l = f(nums, True)\n",
    "        r = f(nums[::-1], False)[::-1]\n",
    "        for i in range(n - 1):\n",
    "            li, ri = min(l[i], r[i]), max(l[i], r[i])\n",
    "            add(0, li, nums[i], nums[i])\n",
    "            add(li, ri, 0, (li + 1) * nums[i])\n",
    "            add(ri, li + ri + 1, -nums[i], (li + ri + 1) * nums[i])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            k[i] += k[i - 1]\n",
    "            b[i] += b[i - 1]\n",
    "\n",
    "        return min(k[i] * i + b[i] for i in range(n))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n=len(nums)\n",
    "        s=list(range(0,n*x,x))  \n",
    "        for i,mn in enumerate(nums): \n",
    "            for j in range(i,n+i): \n",
    "                mn=min(mn,nums[j%n])  \n",
    "                s[j-i]+=mn\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = sum(nums)\n",
    "        price = nums + nums\n",
    "        def check(x,y):\n",
    "            for i in range(len(x)):\n",
    "                x[i] = min(x[i],y[i])\n",
    "            return x\n",
    "        for i in range(1,n):\n",
    "            nums = check(nums,price[i:i+n])\n",
    "            ans = min(ans,x*i + sum(nums))\n",
    "        return ans\n",
    "\n",
    "# 作者：芃芃\n",
    "# 链接：https://leetcode.cn/problems/collecting-chocolates/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        ans = nums[:]\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        minAns = sum(nums)\n",
    "        for i in range(1, n):\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                curIdx = (i + j) % n\n",
    "                tarIdx = j\n",
    "                ans[curIdx] = min(ans[curIdx], nums[tarIdx])\n",
    "                cur += ans[curIdx]\n",
    "            minAns = min(minAns, cur + i * x)\n",
    "        return minAns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        #空间优化 直接在枚举子数组最小值的同时记录答案\n",
    "        n=len(nums)\n",
    "        s=list(range(0,n*x,x)) \n",
    "        for i,mn in enumerate(nums):\n",
    "            for j in range(i,n+i):\n",
    "                mn=min(mn,nums[j%n]) \n",
    "                s[j-i]+=mn   \n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(range(0, n*x , x))\n",
    "        for i,num in enumerate(nums):\n",
    "            for j in range(i,n+i):\n",
    "                num = min(num, nums[j%n])\n",
    "                s[j-i] += num\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        k = [0] * (n + 1)\n",
    "        b = [0] * (n + 1)\n",
    "\n",
    "        def add(l: int, r: int, delta_k: int, delta_b: int):\n",
    "            k[l] += delta_k\n",
    "            k[r] -= delta_k\n",
    "            b[l] += delta_b\n",
    "            b[r] -= delta_b\n",
    "\n",
    "        add(0, n, x, 0)\n",
    "\n",
    "        min_num = min(nums)\n",
    "        min_index = nums.index(min_num)\n",
    "\n",
    "        add(0, n, min_num, min_num)\n",
    "\n",
    "        nums = [nums[(min_index + i) % n] for i in range(1, n)]\n",
    "\n",
    "        def f(a: List[int], left_less: True):\n",
    "            res = [0] * len(a)\n",
    "            stack = []\n",
    "            for i in range(len(a)):\n",
    "                while len(stack) and (\n",
    "                    a[stack[-1]] > a[i] or (a[stack[-1]] == a[i] and not left_less)\n",
    "                ):\n",
    "                    stack.pop()\n",
    "                if len(stack):\n",
    "                    res[i] = i - stack[-1] - 1\n",
    "                else:\n",
    "                    res[i] = i\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "        l = f(nums, True)\n",
    "        r = f(nums[::-1], False)[::-1]\n",
    "        for i in range(n - 1):\n",
    "            li, ri = min(l[i], r[i]), max(l[i], r[i])\n",
    "            add(0, li, nums[i], nums[i])\n",
    "            add(li, ri, 0, (li + 1) * nums[i])\n",
    "            add(ri, li + ri + 1, -nums[i], (li + ri + 1) * nums[i])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            k[i] += k[i - 1]\n",
    "            b[i] += b[i - 1]\n",
    "\n",
    "        return min(k[i] * i + b[i] for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        k = [0] * (n + 1)\n",
    "        b = [0] * (n + 1)\n",
    "\n",
    "        def add(l: int, r: int, delta_k: int, delta_b: int):\n",
    "            k[l] += delta_k\n",
    "            k[r] -= delta_k\n",
    "            b[l] += delta_b\n",
    "            b[r] -= delta_b\n",
    "\n",
    "        add(0, n, x, 0)\n",
    "\n",
    "        min_num = min(nums)\n",
    "        min_index = nums.index(min_num)\n",
    "\n",
    "        add(0, n, min_num, min_num)\n",
    "\n",
    "        nums = [nums[(min_index + i) % n] for i in range(1, n)]\n",
    "\n",
    "        def f(a: List[int], left_less: True):\n",
    "            res = [0] * len(a)\n",
    "            stack = []\n",
    "            for i in range(len(a)):\n",
    "                while len(stack) and (\n",
    "                    a[stack[-1]] > a[i] or (a[stack[-1]] == a[i] and not left_less)\n",
    "                ):\n",
    "                    stack.pop()\n",
    "                if len(stack):\n",
    "                    res[i] = i - stack[-1] - 1\n",
    "                else:\n",
    "                    res[i] = i\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "        l = f(nums, True)\n",
    "        r = f(nums[::-1], False)[::-1]\n",
    "        for i in range(n - 1):\n",
    "            li, ri = min(l[i], r[i]), max(l[i], r[i])\n",
    "            add(0, li, nums[i], nums[i])\n",
    "            add(li, ri, 0, (li + 1) * nums[i])\n",
    "            add(ri, li + ri + 1, -nums[i], (li + ri + 1) * nums[i])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            k[i] += k[i - 1]\n",
    "            b[i] += b[i - 1]\n",
    "\n",
    "        return min(k[i] * i + b[i] for i in range(n))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp= nums.copy()\n",
    "        ans = sum(nums)\n",
    "        for i in range(1,n):\n",
    "            for j in range(n):\n",
    "                dp[j] = min(dp[j], nums[(j-i)%n])\n",
    "            ans = min(ans, sum(dp)+x*i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        k = [0] * (n + 1)\n",
    "        b = [0] * (n + 1)\n",
    "\n",
    "        def add(l: int, r: int, delta_k: int, delta_b: int):\n",
    "            k[l] += delta_k\n",
    "            k[r] -= delta_k\n",
    "            b[l] += delta_b\n",
    "            b[r] -= delta_b\n",
    "\n",
    "        add(0, n, x, 0)\n",
    "\n",
    "        min_num = min(nums)\n",
    "        min_index = nums.index(min_num)\n",
    "\n",
    "        add(0, n, min_num, min_num)\n",
    "\n",
    "        nums = [nums[(min_index + i) % n] for i in range(1, n)]\n",
    "\n",
    "        def f(a: List[int], left_less: True):\n",
    "            res = [0] * len(a)\n",
    "            stack = []\n",
    "            for i in range(len(a)):\n",
    "                while len(stack) and (\n",
    "                    a[stack[-1]] > a[i] or (a[stack[-1]] == a[i] and not left_less)\n",
    "                ):\n",
    "                    stack.pop()\n",
    "                if len(stack):\n",
    "                    res[i] = i - stack[-1] - 1\n",
    "                else:\n",
    "                    res[i] = i\n",
    "                stack.append(i)\n",
    "            return res\n",
    "\n",
    "        l = f(nums, True)\n",
    "        r = f(nums[::-1], False)[::-1]\n",
    "        for i in range(n - 1):\n",
    "            li, ri = min(l[i], r[i]), max(l[i], r[i])\n",
    "            add(0, li, nums[i], nums[i])\n",
    "            add(li, ri, 0, (li + 1) * nums[i])\n",
    "            add(ri, li + ri + 1, -nums[i], (li + ri + 1) * nums[i])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            k[i] += k[i - 1]\n",
    "            b[i] += b[i - 1]\n",
    "\n",
    "        return min(k[i] * i + b[i] for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [i for i in range(0, n * x, x)]  # s[i] 对应操作 i 次的总成本\n",
    "        for i, mn in enumerate(nums):  # 子数组左端点\n",
    "            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）\n",
    "                mn = min(mn, nums[j % n])\n",
    "                s[j - i] += mn  # 累加操作 j-i 次的成本\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        k = [0] * (n + 1)\n",
    "\n",
    "        b = [0] * (n + 1)\n",
    "\n",
    "\n",
    "\n",
    "        def add(l: int, r: int, delta_k: int, delta_b: int):\n",
    "\n",
    "            k[l] += delta_k\n",
    "\n",
    "            k[r] -= delta_k\n",
    "\n",
    "            b[l] += delta_b\n",
    "\n",
    "            b[r] -= delta_b\n",
    "\n",
    "\n",
    "\n",
    "        add(0, n, x, 0)\n",
    "\n",
    "\n",
    "\n",
    "        min_num = min(nums)\n",
    "\n",
    "        min_index = nums.index(min_num)\n",
    "\n",
    "\n",
    "\n",
    "        add(0, n, min_num, min_num)\n",
    "\n",
    "\n",
    "\n",
    "        nums = [nums[(min_index + i) % n] for i in range(1, n)]\n",
    "\n",
    "\n",
    "\n",
    "        def f(a: List[int], left_less: True):\n",
    "\n",
    "            res = [0] * len(a)\n",
    "\n",
    "            stack = []\n",
    "\n",
    "            for i in range(len(a)):\n",
    "\n",
    "                while len(stack) and (\n",
    "\n",
    "                    a[stack[-1]] > a[i] or (a[stack[-1]] == a[i] and not left_less)\n",
    "\n",
    "                ):\n",
    "\n",
    "                    stack.pop()\n",
    "\n",
    "                if len(stack):\n",
    "\n",
    "                    res[i] = i - stack[-1] - 1\n",
    "\n",
    "                else:\n",
    "\n",
    "                    res[i] = i\n",
    "\n",
    "                stack.append(i)\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "\n",
    "        l = f(nums, True)\n",
    "\n",
    "        r = f(nums[::-1], False)[::-1]\n",
    "\n",
    "        for i in range(n - 1):\n",
    "\n",
    "            li, ri = min(l[i], r[i]), max(l[i], r[i])\n",
    "\n",
    "            add(0, li, nums[i], nums[i])\n",
    "\n",
    "            add(li, ri, 0, (li + 1) * nums[i])\n",
    "\n",
    "            add(ri, li + ri + 1, -nums[i], (li + ri + 1) * nums[i])\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            k[i] += k[i - 1]\n",
    "\n",
    "            b[i] += b[i - 1]\n",
    "\n",
    "\n",
    "\n",
    "        return min(k[i] * i + b[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][0] = nums[i]\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                f[i][j] = min(f[i][j - 1], nums[(i - j) % n])\n",
    "        ans = inf\n",
    "        for k in range(n):\n",
    "            res = sum(f[i][k] for i in range(n))\n",
    "            ans = min(ans, res + k * x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n): dp[i][i] = nums[i]\n",
    "        for k in range(1, n):\n",
    "            for i in range(n):\n",
    "                if i+k >= n: break\n",
    "                dp[i][i+k] = min(dp[i][i+k-1], nums[i+k])\n",
    "        # print(dp)\n",
    "        ans = float('inf')\n",
    "        for k in range(n):\n",
    "            tmp = k * x\n",
    "            for i in range(n):\n",
    "                if i+k >= n:\n",
    "                    tmp += min(dp[i][n-1], dp[0][i+k-n])\n",
    "                else:\n",
    "                    tmp += dp[i][i+k]\n",
    "            ans = min(ans, tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        mnval = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                mnval[i][j] = min(mnval[i][j - 1], nums[(i + j) % n])\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            ans = min(ans, sum(mnval[j][i] for j in range(n)) + x * i)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
